Pengacakan: Strategi Perubahan Ukuran

Kebutuhan Rehashing

Untuk menjamin kinerja rata-rata yang diharapkan $O(1)$ untuk pencarian dan penyisipan, faktor muatan (Faktor Muatan ( $\lambda = N/M$ ) harus dibatasi secara ketat, di mana $N$ adalah jumlah elemen dan $M$ adalah kapasitas tabel.

Jika $\lambda$ diperbolehkan tumbuh tanpa batas, tabrakan meningkat secara eksponensial, dan kompleksitas waktu rata-rata menurun menuju $O(N)$ .

Kondisi	Aksi yang Dipicu	Dampak
$\lambda < \lambda_{max}$	Standar $O(1)$ penyisipan	Efisiensi optimal terjaga.
$\lambda \geq \lambda_{max}$	Perubahan Ukuran (Rehashing)	Mengembalikan $O(1)$ kinerja, tetapi menimbulkan biaya sementara $O(N)$ biaya.

Ambang Batas Umum ( $\lambda_{max}$ ): 0.70 hingga 0.75.

Proses Perubahan Ukuran

Perubahan ukuran memerlukan penghitungan ulang indeks hash untuk setiap item yang ada dalam tabel saat ini, proses yang dikenal sebagai Rehashing.

Penentuan Kapasitas Baru: Pilih kapasitas baru $M_{new}$ , biasanya dua kali kapasitas saat ini ( $M_{new} = 2M$ ). Ini memastikan bahwa $\lambda$ adalah separuh dari ambang batas kritis.
Pembuatan Tabel: Alokasikan array tabel hash baru dengan ukuran $M_{new}$ .
Iterasi Item: Putar melalui semua $N$ elemen yang ada dalam tabel lama.
Re-hashing: Untuk setiap kunci $k$ , hitung indeks baru menggunakan modulus yang diperbarui: $\text{indeks}' = h(k) \pmod{M_{new}}$
Penyisipan: Masukkan item ke dalam tabel baru pada $\text{indeks}'$ .

Catatan: Karena modulus berubah, hanya menyalin array tidak mungkin; setiap item harus dimasukkan kembali.

Biaya Amortisasi

Mengapa Perubahan Ukuran adalah $O(N)$

Perubahan ukuran memerlukan pemrosesan semua $N$ elemen, artinya operasi itu sendiri membutuhkan waktu $O(N)$ waktu, yang sementara melanggar tujuan $O(1)$ penyisipan.

Analisis Amortisasi

Kami menggunakan Analisis Amortisasi untuk membenarkan biaya ini. Jika tabel menggandakan ukurannya setiap kali diperbesar (pertumbuhan eksponensial), biaya mahal $O(N)$ akan tersebar di antara sejumlah besar penyisipan yang terjadi di antaranya $O(1)$ penyisipan.

Biaya rata-rata dari setiap penyisipan tunggal, dengan mempertimbangkan perubahan ukuran berkala $O(N)$ perubahan ukuran, tetap $O(1)$ .

📝 Kuis Interaktif

1. Sebuah peta hash memiliki kapasitas $M=50$ dan faktor muatan maksimum $\lambda_{max} = 0.6$ . Pada jumlah elemen berapa ( $N$ ) perubahan ukuran harus dipicu?

A) $N = 25$
B) $N = 30$
C) $N = 31$
D) $N = 50$

2. Selama perubahan ukuran, mengapa kita tidak bisa sekadar menyalin elemen dari tabel lama ke tabel baru yang lebih besar?

A) Lebih lambat secara komputasi daripada rehashing.
B) Indeks hash bergantung pada kapasitas tabel ( $M$ ), yang telah berubah.
C) Akan menyebabkan fragmentasi memori.
D) Data lama berada dalam status baca saja.

3. Berapa kompleksitas waktu amortisasi dari penyisipan dalam tabel hash yang menggandakan ukurannya saat perubahan ukuran?

A) $O(N)$
B) $O(1)$
C) $O(\log N)$
D) $O(N \log N)$

4. Apa konsekuensi utama dari tidak melakukan perubahan ukuran tabel hash ketika faktor muatannya terlalu tinggi?

A) Kinerja menurun menuju $O(N)$ karena peningkatan tabrakan.
B) Tabel akan kehabisan memori segera.
C) Fungsi hash itu sendiri menjadi tidak valid.
D) Tabel secara otomatis menghapus elemen tertua.